package com.dy.排序和搜索.中级.颜色分类;

/*
颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？

 */
public class Solution {
    public void sortColors(int[] nums) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) count0++;
            else if (nums[i] == 1) count1++;
            else if (nums[i] == 2) count2++;
        }
        int i = 0;
        for (; i < count0; i++) {
            nums[i] = 0;
        }
        for (int j = 0; j < count1; j++) {
            nums[i++] = 1;
        }
        for (int j = 0; j < count2; j++) {
            nums[i++] = 2;
        }
    }

    /*
    一个指针用于记录头部0 的位置，一个指针记录末尾最后2的位置，遇到0就交换，遇到2交换，1不交换
     */
    public void sortColors2(int[] nums) {
        int index0 = 0;
        int index2 = nums.length - 1;
        for (int i = 0; i <= index2; ) {
            if (nums[i] == 0 && i != index0) swap(nums, i, index0++);
            else if (nums[i] == 2) swap(nums, i, index2--);
            else i++;


        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
